package il.ac.tau.cg.ex3.utils.octree;

import il.ac.tau.cg.ex3.math.shapes.Bounded;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Octree<T extends Bounded>
{
	private static final int MAX_SUBTREES = 8;
	
	private BoundingBox boundingBox;
	
	private List<T> items;
	private List<Octree<T>> subtrees;
	
	public Octree(BoundingBox boundingBox)
	{
		this.boundingBox = boundingBox.clone();
		
		this.items = new ArrayList<T>();
		this.subtrees = new ArrayList<Octree<T>>();
		
		for (int i = 0; i < MAX_SUBTREES; i++)
		{
			this.subtrees.add(null);
		}
	}
	
	public BoundingBox getBoundingBox()
	{
		return boundingBox;
	}
	
	public List<T> getItems()
	{
		return items;
	}
	
	public Octree<T> getSubtree(int x, int y, int z)
	{
		return subtrees.get(getSubtreeIndex(x, y, z));
	}
	
	public void insert(Collection<? extends T> items)
	{
		for (T item : items)
		{
			insert(item);
		}
	}
	
	public void insert(T item)
	{
		BoundingBox itemBounds = item.getBoundingBox();
		
		if (!boundingBox.contains(itemBounds))
		{
			throw new IllegalArgumentException();
		}
		
		double xHalfSpan = (boundingBox.getMaxX() - boundingBox.getMinX()) / 2.0;
		double yHalfSpan = (boundingBox.getMaxY() - boundingBox.getMinY()) / 2.0;
		double zHalfSpan = (boundingBox.getMaxZ() - boundingBox.getMinZ()) / 2.0;
		
		for (int x = 0; x < 2; x++)
		{
			double minX = (x == 0 ? boundingBox.getMinX() : boundingBox.getMinX() + xHalfSpan);
			double maxX = minX + xHalfSpan;
			
			for (int y = 0; y < 2; y++)
			{
				double minY = (y == 0 ? boundingBox.getMinY() : boundingBox.getMinY() + yHalfSpan);
				double maxY = minY + yHalfSpan;
				
				for (int z = 0; z < 2; z++)
				{
					double minZ = (z == 0 ? boundingBox.getMinZ() : boundingBox.getMinZ() + zHalfSpan);
					double maxZ = minZ + zHalfSpan;
					
					BoundingBox subBox = new BoundingBox(minX, maxX, minY, maxY, minZ, maxZ);
					
					if (subBox.contains(itemBounds))
					{
						int subtreeIndex = getSubtreeIndex(x, y, z);
						Octree<T> subtree = subtrees.get(subtreeIndex);
						
						if (subtree == null)
						{
							subtree = new Octree<T>(subBox);
							subtrees.set(subtreeIndex, subtree);
						}
						
						subtree.insert(item);
						
						return;
					}
				}
			}
		}
		
		items.add(item);
	}
	
	private int getSubtreeIndex(int x, int y, int z)
	{
		return (x * 4 + y * 2 + z);
	}
}
